/*
 * Maximum Path Sum II Solution.
 */

package Graph;

/**
 * Implementation of a weighted graph using adjacency list representation.
 * Based on material in the CLRS text.
 * 
 * @author Michael Silva
 */

public class WeightedAdjacencyListGraph extends AdjacencyListGraph {
    
    /**
     * Static nested class that defines a weighted edge for use in an adjacency
     * list.
     */
    public static class WeightedEdge extends Edge                               
    {
        /** Weight of the edge. */
        private int weight;
        
        /**
         * Overrides {@link AdjacencyListGraph.Edge} to include a weight.
         * 
         * @param vert The vertex adjacent.
         * @param weight Weight of the edge.
         * @param successor The next edge.
         */
        public WeightedEdge(Vertex vert, int weight, Edge successor)
        {
            super(vert, successor);
            this.weight = weight;
        }
        
        /**
         * Sets the weight of the <code>Edge</code>.
         *
         * @param weight integer weight of the edge.
         */
        public void setWeight(int weight) 
        {
            this.weight = weight;
        }
        
        /**
         * Tells the weight of the given <code>Edge</code>.
         * 
         * @return Weight of the edge.
         */
        public int getWeight()
        {
            return weight;
        }
    }
       
    
    /**
     * Create a new empty weighted graph with the default capacity.
     */
    public WeightedAdjacencyListGraph ()
    {
        super();
    }
    
    
    /**
     * Create a new empty weighted graph with the given capacity.
     * 
     * @param capacity Number of vertices in the graph
     * @throws IllegalArgumentException 
     */
    public WeightedAdjacencyListGraph(int capacity) 
                throws IllegalArgumentException
    {
        super(capacity);
    }
    
    
    /**
     * Add a weighted edge between the given vertices.
     * 
     * @param uIndex Index of a <code>Vertex</code> in the graph.
     * @param vIndex Index an adjacent <code>Vertex</code>.
     * @param weight Weight of the edge.
     */
    public void addEdge(int uIndex, int vIndex, int weight)
    {
        addEdge(adjList[uIndex].thisVertex, adjList[vIndex].thisVertex, weight);
    }
    
    
    /**
     * Add a weighted edge between the given vertices.
     * 
     * @param u <code>Vertex</code> in the graph.
     * @param v <code>Vertex</code> adjacent vertex.
     * @param weight Weight of the edge.
     */
    public void addEdge(Vertex u, Vertex v, int weight)
    {
        int uIndex = u.getIdentifier();
        
        // Create the new weighted edge.
        WeightedEdge edge = new WeightedEdge(v, weight, adjList[uIndex].head);
        
        // Add the weighted edge to the adjacency list.
        adjList[uIndex].head = edge;
    }
   
    
    /**
     * Provides a string representation of the graph in adjacency list form.
     * Output is for the form:
     *   [VertexId]->(IncidentEdgeId_1,Weight)(IncidentEdgeId_2,Weight)(...)
     * 
     * @return  String representation of the graph.
     */ 
    @Override
    public String toString()
    {
        String str = "";
        
        for (int i=0; i < adjList.length; i++)
        {
            AdjListEntry entry = adjList[i];
            
            // Print AdjListEntry.Vector
            str += "[" + entry.thisVertex.getIdentifier() + "]->";
            
            // Print all the edges
            WeightedEdge eitr = (WeightedEdge)entry.head;
            while (eitr != null) {
                str += "[" + eitr.vert.getIdentifier() + "," +
                       eitr.getWeight() + "]";
                
                eitr = (WeightedEdge)eitr.successor;
            }
                
            str += "\n";
            
        }
        
        return str;
    }
    
}
